#include <bits/stdc++.h>
using namespace std;
#define int long long

int c[1000007], pre[10000007], tot;
bool b[10000007];

int lcm(int a, int b) {
	return a / __gcd(a, b) * b;
}

int togo(int a, int b) {
	if (a == b) return 0;
	return lcm(a, b);
}


void solve() {
	int x, y;
	cin >> x >> y;
	if (__gcd(x, y) == 1) {
		if (!b[x] && !b[y]) {
			cout << togo(x, 2) + togo(2, y) << "\n";
		} else if (b[x] && !b[y]) {
			cout << togo(x, pre[x]) + togo(pre[x], 2) + togo(2, y) << "\n";
		}  else if (!b[x] && b[y]) {
			cout << togo(y, pre[y]) + togo(pre[y], 2) + togo(2, x) << "\n";
		} else {
			cout << togo(x, pre[x]) + togo(pre[x], 2) + togo(2, pre[y]) + togo(pre[y], y) << "\n";
		}
	} else {
		if (y % x == 0) {
			cout << y << "\n";
			return;
		}
		cout << x + y << "\n";
	}
}
/*
	9 16
	
*/

signed main() {
	freopen("never.in", "r", stdin);
	freopen("never.out", "w", stdout);
	ios::sync_with_stdio(0); cin.tie(0);
	for (int i = 2; i <= 10000000; ++i) {
		if (!b[i]) c[++tot] = i;
		for (int j = 1; j <= tot && c[j] * i <= 10000000; ++j) {
			b[c[j] * i] = 1;
			pre[c[j] * i] = c[j];
			if (i % c[j] == 0) break;
		}
	}
	int tc; cin >> tc; while (tc--) solve();
	return 0;
}
